/**
 * https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
 * 数据流中第K个大元素
 */
class KthLargest {
  private k: number;
  private minHead: MinHead;
  constructor(k: number, nums: number[]) {
    this.k = k;
    this.minHead = new MinHead([]);

    // 添加
    for (let v of nums) {
      this.add(v);
    }
  }

  add(val: number): number {
    this.minHead.offer(val);

    // 如果大于了k, 弹出最顶层
    if (this.minHead.size() > this.k) {
      this.minHead.remove();
    }

    // 查看最顶层的元素
    return this.minHead.peek();
  }
}

/**
 * 最小堆
 */
class MinHead {
  constructor(public arr: number[]) {
    // 批量建堆
  }

  /**
   * 获取长度
   * @returns
   */
  size() {
    return this.arr.length;
  }

  /**
   * 添加元素
   */
  offer(item: number) {
    // 添加到头部, 并对0位置下滤处理
    this.arr.push(item);
    this.up(this.size() - 1);
  }

  /**
   * 批量建堆
   */
  heapify() {
    const sizes = (this.arr.length >> 1) - 1;
    for (let i = sizes; i >= 0; i--) {
      // 下滤
      this.down(i);
    }
  }

  /**
   * 获取父元素的索引
   * @param i
   */
  private getParI(i: number) {
    return ~~((i - 1) >> 1);
  }

  /**
   * 上滤
   * @param index 
   * @returns 
   */
  up(index: number) {
    if (index <= 0) return;
    // 父元素的索引
    let parI = this.getParI(index);
    // 没有父元素
    if (parI < 0) return;
    // debugger
    while (parI >= 0) {
      // 父元素存在
      const min = this.getMin(index, parI);
      if (min === index) {
        // 比父元素小，交换两个元素的位置
        this.swap(index, parI);
        // 改变parI和index
        index = parI;
        parI = this.getParI(parI);
      } else {
        // 比父元素小，直接结束循环
        break;
      }
    }
  }

  /**
   * 下滤
   * @param i
   */
  down(i: number) {
    // 获取非叶子结点的数量
    const sizes = this.arr.length >> 1;
    while (i < sizes) {
      // 获取左右孩子的索引
      const lI = this.getLeftIndex(i);
      const rI = this.getRightIndex(i);

      // 获取左右孩子中比较小的索引
      const minI = this.getMin(lI, rI);

      // 当前自己比孩子还要小, 直接返回即可
      if (this.getMin(i, minI) === i) return;

      // 和孩子交换
      this.swap(minI, i);

      //处理孩子
      i = minI;
    }
  }

  /**
   * 删除堆顶
   */
  remove() {
    if (this.size() == 0) return null;
    const arr = this.arr;

    // 让最后一个元素覆盖第一个值, 并且将最后一个置为空
    const removeItem = arr[0];
    const last = arr.pop()!;
    if (this.size() !== 0) {
      arr[0] = last;

      // 对0位置下滤
      this.down(0);
    }

    return removeItem;
  }

  /**
   * 查看堆顶
   * @returns
   */
  peek() {
    return this.arr[0];
  }

  /**
   * 获取左孩子的索引
   * @param i
   * @returns
   */
  getLeftIndex(i: number) {
    return (i << 1) + 1;
  }

  /**
   * 获取右孩子的索引
   * @param i
   */
  getRightIndex(i: number) {
    return (i << 1) + 2;
  }

  /**
   * 交换两个元素
   * @param l
   * @param r
   */
  swap(l: number, r: number) {
    [this.arr[l], this.arr[r]] = [this.arr[r], this.arr[l]];
  }

  /**
   * 获取左右孩子中比较小的哪个
   * @param li
   * @param ri
   * @returns
   */
  getMin(li: number, ri: number) {
    // 右孩子越界了
    if (ri >= this.arr.length) return li;

    const l = this.arr[li];
    const r = this.arr[ri];

    // 谁小返回谁
    return l > r ? ri : li;
  }
}

// new MinHead([4, 5, 8, 2])
new KthLargest(3, [4, 5, 8, 2]);
